package Class024;

import Class021.Merge;
import Utils.ArrayUtils;

import java.util.Arrays;

//在一个无序数组上寻找排在第n个的数是什么
//快排的划分思想下，貌似复杂度是O(N * logN)
//实际上加入随机过程后，可以收敛到O(N)
//测试结果基本符合
public class RandomSelect {
    public static void main(String[] args) {
        test();
    }

    public static int right(int[] arr, int pos) {
        if (pos < 0 || pos > arr.length - 1) return -1;
        Arrays.sort(arr);
        return arr[pos];
    }

    public static int[] partition(int[] arr, int l, int r, int pivot) {
        int less = l - 1, more = r + 1, index = l;
        while (index < more) {
            if (arr[index] < pivot) {
                ArrayUtils.swap(arr, index++, ++less);
            } else if (arr[index] > pivot) {
                ArrayUtils.swap(arr, index, --more);
            } else {
                index++;
            }
        }
        return new int[]{less + 1, more - 1};
    }

    public static int findNum(int[] arr, int l, int r, int pos) {
        if (pos < 0 || pos > arr.length - 1) return -1;
//        int pivot = arr[(int) (Math.random() * (r - l + 1)) + l];
//        int[] range = partition(arr, l, r, pivot);
//
//        if (range[0] > pos) {
//            return findNum(arr, l, range[0] - 1, pos);
//        } else if (range[1] < pos) {
//            return findNum(arr, range[1] + 1, r, pos);
//        } else {
//            return arr[range[0]];
//        }

        //迭代更快
        int left = l, right = r, ans = - 1;
        int[] range = null;
        int pivot;
        while(left <= right) {
            pivot = arr[(int) (Math.random() * (right - left + 1)) + left];
            range = partition(arr, left, right, pivot);
            if (range[0] > pos) {
                right = range[0] - 1;
            } else if (range[1] < pos) {
                left = range[1] + 1;
            } else {
                ans = arr[range[0]];
                break;
            }
        }
        return ans;
    }

    public static int locate(int[] arr, int pos) {
        return findNum(arr, 0, arr.length - 1, pos);
    }

    public static void test() {
        int time = 1000;
        int amount = 30000, max = 1000;
        int errTime = 0;
        System.out.println("Correctness Test:");
        for (int i = 0; i < time; i++) {
            int[] base = ArrayUtils.generateArray(amount, max);
            int[] better = Arrays.copyOf(base, base.length);
            int[] right = Arrays.copyOf(base, base.length);
            int pos = (int) (Math.random() * (max + 10)) - 5;

            int b = locate(better, pos);
            int r = right(right, pos);
            if (b != r) {
                System.out.println(Arrays.toString(right));
                System.out.println("Want to find the num on:" + pos);
                System.out.println("Should be:");
                System.out.println(r);
                System.out.println("Wrong answer:");
                System.out.println(b);
                errTime++;
            }
        }
        if (errTime == 0) {
            System.out.println("All clear.");
        } else {
            System.out.println("Errors:" + errTime + "/" + time);
            System.out.println("Accuracy:" + (time - errTime) * 1.0 / time);
            return;
        }

        System.out.println("Time test:");
        long s, e;
        s = System.currentTimeMillis();
        for (int i = 0; i < time; i++) {
            int[] base = ArrayUtils.generateArray(amount, max);
            int pos = (int) (Math.random() * (max + 10)) - 5;
            locate(base, pos);
        }
        e = System.currentTimeMillis();
        System.out.println("Better:" + (e - s) + "ms");

        s = System.currentTimeMillis();
        for (int i = 0; i < time; i++) {
            int[] base = ArrayUtils.generateArray(amount, max);
            int pos = (int) (Math.random() * (max + 10)) - 5;
            right(base, pos);
        }
        e = System.currentTimeMillis();
        System.out.println("Poor:" + (e - s) + "ms");
    }

}
